#include<stdio.h>
#include<stdlib.h>
int a[] = {100,10,400,382,200};
int n = 5;
int getMax()
{
    int max = a[0];
    for(int i = 1 ; i < n; i++)
    {
        if(a[i] > max)
            max = a[i];
    }
    return max;
}
void countsort(int exp)
{
    int output[n], i = 0 ;
    int count[10] = {0};
    
    for(i = 0; i < n ; i++)
        count[a[i]/exp%10]++;
    
    for(i = 1; i < 10; i++)
        count[i] = count[i] + count[i - 1];
    
    for(i = n-1; i >= 0 ; i--)
    {
        int digit = (a[i]/exp)%10;
        output[count[digit]-1] = a[i];
        count[digit]--;
    }
    for(i = 0; i < n; i++)
    {
        a[i] = output[i];
    }
}
void RadixSort()
{
    int max = getMax();
    for(int exp = 1; max/exp > 0; exp*=10)
        countsort(exp);
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void heapify(int a[], int n, int i)
{
    int largest = i;
    int left = 2*i+1;
    int right = 2*i+2;
    
    if(left < n && a[left] > a[largest])
     largest = left;
    
    if(right < n && a[right] > a[largest])
     largest = right;
    
    if ( largest != i)
    {
        swap(&a[largest], &a[i]);
        heapify(a, n, largest);
    }
}
void heapsort(int a[], int n)
{
    for(int i = n/2-1; i >=0 ; i--)
        heapify(a, n, i);
    
    for(int i = n-1; i>=0; i--)
    {
        swap(&a[0], &a[i]);
        heapify(a, i, 0);
    }
}
int main()
{
    heapsort(a, n);
    for(int i = 0; i < n; i++)
        printf("%d ", a[i]);
    return 0;
}